package com.shuo.dsa.sort;

import java.util.Arrays;

/**
 * Created by shuoGG on 2018/9/23 0023
 */
public class ShuoGGQuickSort {
    public static void main(String[] args) {
        int[] arrays = {2, 3, 1, 4, 3, 5, 1, 6, 1, 2, 3, 7, 2, 3};
        quickSort(arrays, 0, arrays.length - 1);
        System.out.println(Arrays.toString(arrays));
    }

    // pivot的左边都比pivot小, 右边都比pivot大
    public static void quickSort(int[] arr, int L, int R) {
        int i = L;
        int j = R;
        int pivot = arr[(L + R) / 2];
        while (i <= j) {
            while (pivot > arr[i])
                i++;
            while (pivot < arr[j])
                j--;
//            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
//            }
//            if (L < j)
                quickSort(arr, L, j);
//            if (R > i)
                quickSort(arr, i, R);
        }
    }

    public static void swap(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}
